#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣918. 环形子数组的最大和
// 【难度】中等
// 【提交】2025.10.09 10:00 https://leetcode.cn/problems/maximum-sum-circular-subarray/submissions/669100617/
// 【标签】动态规划；数组
class Solution_LC0918 {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        int pMax = nums[0], pMin = nums[0], rMax = nums[0], rMin = nums[0];
        int sum = nums[0];
        for(int i = 1; i < n; ++i) {
            pMax = max(pMax + nums[i], nums[i]);
            pMin = min(pMin + nums[i], nums[i]);
            rMax = max(rMax, pMax);
            rMin = min(rMin, pMin);
            sum += nums[i];
        }
        if(rMax < 0) {
            return rMax;
        } else {
            return max(rMax, sum - rMin);
        }
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个环形整数数组nums（即数组首尾相连），找出一个具有最大和的连续子数组，返回其最大和。
 * 模型：动态规划，通过同时计算最大子数组和和最小子数组和来解决环形数组问题。
 * 
 * 二、标准解法状态设计
 * 1. 使用Kadane算法同时计算最大子数组和(rMax)和最小子数组和(rMin)。
 * 2. 计算数组总和(sum)。
 * 3. 如果所有元素都是负数(rMax < 0)，直接返回rMax。
 * 4. 否则，返回max(rMax, sum - rMin)，考虑环形情况。
 * 
 * 三、你的实现思路
 * 使用改进的Kadane算法，在一次遍历中同时计算最大子数组和和最小子数组和。
 * 通过比较常规最大子数组和与环形情况下的最大子数组和，得到最终结果。
 * 
 * 四、逐行注释（带细节提醒）
 * int pMax = nums[0], pMin = nums[0], rMax = nums[0], rMin = nums[0]; // 初始化变量
 * int sum = nums[0]; // 初始化数组总和
 * 
 * for(int i = 1; i < n; ++i) { // 遍历数组
 *     pMax = max(pMax + nums[i], nums[i]); // 更新当前最大子数组和
 *     pMin = min(pMin + nums[i], nums[i]); // 更新当前最小子数组和
 *     rMax = max(rMax, pMax); // 更新全局最大子数组和
 *     rMin = min(rMin, pMin); // 更新全局最小子数组和
 *     sum += nums[i]; // 累加数组总和
 * }
 * 
 * if(rMax < 0) { // 如果所有元素都是负数
 *     return rMax; // 直接返回最大子数组和
 * } else { // 否则
 *     return max(rMax, sum - rMin); // 返回常规和环形情况下的较大值
 * }
 * 
 * 五、正确性证明
 * 环形数组的最大子数组和有两种情况：
 * 1. 常规情况：最大子数组不跨越数组边界，此时结果等于rMax。
 * 2. 环形情况：最大子数组跨越数组边界，此时结果等于sum - rMin（因为跨越边界意味着中间部分是最小子数组）。
 * 当所有元素都是负数时，最小子数组和等于总和，此时sum - rMin = 0，但最大子数组和应该是最大的负数，所以直接返回rMax。
 * 
 * 六、复杂度
 * 时间：O(n)，只需遍历数组一次。
 * 空间：O(1)，只使用了常数级别的额外空间。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 时间复杂度低，只需一次遍历；
 *   - 空间复杂度低，无需额外数组；
 *   - 算法巧妙，同时处理常规和环形情况。
 * 缺点：
 *   - 算法理解起来有一定难度；
 *   - 需要同时维护多个变量。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (nums.empty()) return 0;
 * 2. 使用更明确的变量名（如 currMax 代替 pMax）来增强可读性；
 * 3. 对于教学场景，可以添加注释解释环形情况的处理原理。
 * 
 * 九、一句话总结
 * 通过同时计算最大子数组和和最小子数组和，你的实现巧妙地解决了环形数组的最大子数组和问题，
 * 展现了动态规划在复杂场景下的应用能力。
 */